\section{Indirect Methods}

\subsection{Calculus of Variations}

We will begin by restating the optimal control problem. We will to find an admissible control sequence $\ac^*$ which causes the system 
\begin{equation}
    \stdot = \f(\st(t),\ac(t),t)
\end{equation}
to follow an \textit{admissible} trajectory $\st^*$ that minimizes the functional 
\begin{equation}
    \J = \cost_f(\st(t_f),t_f) + \int_{t_0}^{t_f} \cost(\st(t),\ac(t),t) dt.
\end{equation}
To find the minima of functions of a finite number of real numbers, we rely on the first order optimality conditions to find candidate minima, and use higher order derivatives to determine whether a point is a local minimum. Because we are minimizing a function that maps from some $n$ dimensional space to a scalar, candidate points have zero gradient in each of these dimensions. However, in the optimal control problem, we have a cost \textit{functional}, which maps functions to scalars. This is immediately problematic for our first order conditions --- we are required to check the necessary condition at infinite points. The necessary notion of optimality conditions for functionals is provided by calculus of variations.

Concretely, we define a functional $\J$ as a rule of correspondence assigning each function $\st$ in a class $\Omega$ (the domain) to a unique real number. The functional $\J$ is linear if and only if 
\begin{equation}
    \J(\alpha_1 \st_1 + \alpha_2 \st_2) = \alpha_1 \J(\st_1) + \alpha_2 \J(\st_2)
\end{equation}
for all $\st_1, \st_2, \alpha_1 \st_1 + \alpha_2 \st_2$ in $\Omega$. We must now define a notion of ``closeness'' for functions. Intuitively, two points being close together has an immediate geometric interpretation. We first define the norm of a function. The norm of a function is a rule of correspondence that assigns each $\st \in \Omega$, defined over $t \in [t_0,t_f]$, a real number. The norm of $\st$, which we denote $\|\st\|$, satisfies:
\begin{enumerate}
    \item $\|\st\| \geq 0$, and $\|\st\|=0$ iff $\st(t) = 0$ for all $t \in [t_0,t_f]$
    \item $\|\alpha \st\| = |\alpha| \|\st\|$ for all real numbers $\alpha$
    \item $\|\st_1 + \st_2\| \leq \|\st_1\| + \|\st_2\|$.
\end{enumerate}
To compare the closeness of two functions $\bm{y}, \bm{z}$, we let $\st(t) = \bm{y}(t) - \bm{z}(t)$. Thus, for two identical functions, $\|\st\|$ is zero. Generally, a norm will be small for ``close'' functions, and large for ``far apart'' functions. However, there exist many possible definitions of norms that satisfy the above conditions. 

\subsubsection{Extrema for Functionals}

A functional $\J$ with domain $\Omega$ has a local minimum at $\st^* \in \Omega$ if there exists an $\epsilon > 0$ such that $\J(\st) \geq \J(\st^*)$ for all $\st \in \Omega$ such that $\|\st - \st^*\| < \epsilon$. Maxima are defined similarly, just with $\J(\st) \leq \J(\st^*)$. 

Analogously to optimization of functions, we define the variation of the functional as
\begin{equation}
    \Delta \J(\st,\delta \st) \vcentcolon= \J(\st + \delta \st) - \J(\st)
\end{equation}
where $\delta \st(t)$ is the \textit{variation} of $\st(t)$. The increment of a functional can be written as 
\begin{equation}
    \Delta \J(\st,\delta \st) = \delta \J(\st,\delta \st) + g(\st,\delta \st) \|\delta \st\|
\end{equation}
where $\delta \J$ is linear in $\delta \st$. If 
\begin{equation}
    \lim_{\|\delta \st \| \to 0} \{g(\st,\delta \st)\} = 0
\end{equation}
then $\J$ is said to be differentiable on $\st$ and $\delta \J$ is the variation of $\J$ at $\st$. 
We can now state the \textit{fundamental theorem of the calculus of variations}. 

\begin{theorem}[Fundamental Theorem of CoV]
Let $\st(t)$ be a vector function of $t$ in the class $\Omega$, and $\J(\st)$ be a differentiable functional of $\st$. Assume that the functions in $\Omega$ are not constrained by any boundaries. If $\st^*$ is an extremal, the variation of $\J$ must vanish at $\st^*$, that is $\delta \J(\st^*, \delta \st) = 0$ for all admissible $\delta \st$ (i.e. such that $\st + \delta \st \in \Omega$).
\end{theorem}

\begin{proof}
\cite{kirk2012optimal}, Section 4.1.
\end{proof}

We will now look at how calculus of variations may be leveraged to approach practical problems. Let $x$ be a scalar continuous function in $C^1$. We would like to find a function $x^*$ for which the functional 
\begin{equation}
    \J(s) = \int_{t_0}^{t_f} g(x(t),x(t),t) dt
\end{equation}
has a relative extremum. We will assume $g \in C^2$, that $t_0,t_f$ are fixed, and $x_0, x_f$ are fixed. Let $\st$ be any curve in $\Omega$, and we will write the variation $\delta\J$ from the increment
\begin{align}
    \Delta \J(x,\delta x) &= \J(x + \delta x) - \J(x)\\
    &= \int_{t_0}^{t_f} g(x + \delta x, \dot{x} + \delta \dot{x}, t) dt - \int_{t_0}^{t_f} g(x,\dot{x},t) dt\\
    &= \int_{t_0}^{t_f} g(x + \delta x, \dot{x} + \delta \dot{x}, t) - g(x,\dot{x},t) dt.
\end{align}
Expanding via Taylor series, we get
\begin{equation}
    \Delta J(x,\delta x) = \int_{t_0}^{t_f} g(x,\dot{x},t) + \underbrace{\frac{\partial g}{\partial x}}_{g_{x}} (x,\dot{x}, t) \delta x + \underbrace{\frac{\partial g}{\partial \dot{x}}}_{g_{\dot{x}}} (x,\dot{x}, t) \delta \dot{x} + o(\delta x, \delta \dot{x}) - g(x,\dot{x},t) dt
\end{equation}
which yields the variation
\begin{equation}
    \delta \J = \int_{t_0}^{t_f} g_{x}(x,\dot{x},t) \delta x + g_{\dot{x}}(x,\dot{x},t)\delta \dot{x} \,\,dt.
\end{equation}
Integrating by parts, we have 
\begin{equation}
    \delta \J = \int_{t_0}^{t_f} \left[ g_{x}(x,\dot{x},t) - \frac{d}{dt} g_{\dot{x}}(x,\dot{x},t)\right] \delta x \delta t + [g_{\dot{x}}(x,\dot{x},t)\delta x(t)]_{t_0}^{t_f}.
\end{equation}
We have assumed $x(t_0), x(t_f)$ given, and thus $\delta x(t_0) = 0$, $\delta x(t_f) = 0$. Considering an extremal curve, applying the CoV theorem yields
\begin{equation}
    \int_{t_0}^{t_f} \left[ g_{x}(x,\dot{x},t) - \frac{d}{dt} g_{\dot{x}}(x,\dot{x},t)\right] \delta x \delta t.
    \label{eq:euler_int}
\end{equation}
We can now state the fundamental lemma of CoV. We will state it for vector functions, although our derivation was for the scalar case. 

\begin{lemma}[Fundamental Lemma of CoV]
If a function $h$ is continuous and 
\begin{equation}
    \int_{t_0}^{t_f} h(t) \delta \st(t) dt = 0
\end{equation}
for every function $\delta \st$ that is continuous in the interval $[t_0,t_f]$, then $h$ must be zero everywhere in the interval $[t_0,t_f]$.
\end{lemma}

\begin{proof}
\cite{kirk2012optimal}, Section 4.2.
\end{proof}

Applying the fundamental lemma, we find that a necessary condition for $\st^*$ being an extremal is 
\begin{equation}
    g_{\st}(\st,\stdot,t) - \frac{d}{dt} g_{\stdot}(\st,\stdot,t) = 0
\end{equation}
for all $t \in [t_0, t_f]$, which is the \textit{Euler equation}. This is a nonlinear, time-varying second-order ordinary differential equation with split boundary conditions (at $\st(t_0)$ and $\st(t_f)$).

\subsubsection{Generalized Boundary Conditions}

In the previous subsection, we assumed that $t_0, t_f, \st(t_0), \st(t_f)$ were all given. We will now relax that assumption. In particular, $t_f$ may be fixed or free, and each component of $\st(t_f)$ may be fixed or free. 

We begin by writing the variation around $\st^*$
\begin{align}
\delta \J &= \left[ g_{\stdot}(\st^*(t_f),\stdot^*(t_f),t_f) \right]^T \delta \st(t_f) + 
\left[ g(\st^*(t_f),\stdot^*(t_f),t_f) \right]^T \delta t_f\\
& \qquad + \int_{t_0}^{t_f} \left[ g_{\st}(\st^*,\stdot^*,t) - \frac{d}{dt} g_{\stdot}(\st^*,\stdot^*,t)\right]^T \delta \st \delta t \nonumber
\end{align}
by using the same integration by parts approach as before. Note that for fixed $t_f$ and $\st(t_f)$, the variations $\delta t_f$ and $\delta \st(t_f)$ vanish, and so we are left with (\ref{eq:euler_int}). Because $\delta t_f$ and $\delta \st(t_f)$ do not vanish in this case, we are left with additional boundary conditions that must be satisfied. Note that 
\begin{equation}
    \delta \st_f = \delta \st(t_f) + \stdot^*(t_f) \delta t_f
\end{equation}
and substituting this, we have
\begin{align}
\delta \J &= \left[ g_{\stdot}(\st^*(t_f),\stdot^*(t_f),t_f) \right]^T \delta \st_f + 
\left[ g(\st^*(t_f),\stdot^*(t_f),t_f) - g^T_{\stdot}(\st^*(t_f),\stdot^*(t_f),t_f) \stdot^*(t_f) \right] \delta t_f\\
& \qquad + \int_{t_0}^{t_f} \left[ g_{\st}(\st^*,\stdot^*,t) - \frac{d}{dt} g_{\stdot}(\st^*,\stdot^*,t)\right] \delta \st \delta t \nonumber.
\end{align}
Stationarity of this variation thus requires 
\begin{equation}
    g_{\stdot}(\st^*(t_f),\stdot^*(t_f),t_f) = 0
\end{equation} 
if $\st_f$ is free, and 
\begin{equation}
    g(\st^*(t_f),\stdot^*(t_f),t_f) - g^T_{\stdot}(\st^*(t_f),\stdot^*(t_f),t_f) \stdot^*(t_f) = 0
\end{equation}
if $t_f$ is free, in addition to the Euler equation being satisfied. For a complete reference on the boundary conditions associated with a variety of problem specifications, we refer the reader to Section 4.3 of \cite{kirk2012optimal}.

% TODO add table

\subsubsection{Constrained Extrema}

Previously, we have not considered constraints in the variational problem. However, constraints (and in particular, dynamics constraints) are central to most optimal control problems. Let $\bm{w} \in \R^{n+m}$ be a vector function in $C^1$. As previously, we would like to find a function $\bm{w}^*$ for which the functional 
\begin{equation}
    \J(\bm{w}) = \int_{t_0}^{t_f} g(\bm{w}(t),\dot{\bm{w}}(t),t) dt
\end{equation}
has a relative extremum, although we additionally introduce the constraints 
\begin{equation}
    \f_i(\bm{w}(t), \dot{\bm{w}}(t),t) = 0, \quad i = 1, \ldots, n.
\end{equation}
We will again assume $g \in C^2$ and that $t_0, \bm{w}(t_0)$ are fixed. Note that as a result of these $n$ constraints, only $m$ of the $n+m$ components of $\bm{w}$ are independent. 

One approach to solving this constrained problem is re-writing the $n$ dependent components of $\bm{w}$ in terms of the $m$ independent components. However, the nonlinearity of the constraints typically makes this infeasible. Instead, we will turn to Lagrange multipliers. We will write our \textit{augmented functional} as 
\begin{equation}
    \hat{g}(\bm{w}(t),\dot{\bm{w}}(t),\bm{p}(t),t) \vcentcolon = g(\bm{w}(t),\dot{\bm{w}}(t),t) + \bm{p}^T(t) \bm{f}(\bm{w}(t),\dot{\bm{w}}(t),t)
\end{equation}
where $\bm{p}(t)$ are Lagrange multipliers that are functions of time. Based on this, a necessary condition for optimality is 
\begin{equation}
    \hat{g}_{\bm{w}}(\bm{w}^*(t),\dot{\bm{w}}^*(t),\bm{p}^*(t),t) - \frac{d}{dt} \hat{g}_{\dot{\bm{w}}}(\bm{w}^*(t),\dot{\bm{w}}^*(t),\bm{p}^*(t),t) = 0
\end{equation}
with 
\begin{equation}
    \bm{f}(\bm{w}^*(t), \dot{\bm{w}}^*(t),t) = 0.
\end{equation}


\subsection{Indirect Methods for Optimal Control}

Having built the foundations of functional optimization via calculus of variations, we will now derive the necessary conditions for optimal control under the assumption that the admissible controls are not bounded. The problem, as previously stated, is to find an \textit{admissible control} $\ac^*$ which causes the system 
\begin{equation}
    \stdot(t) = \f(\st(t),\ac(t),t)
\end{equation}
to follow an \textit{admissible trajectory} $\st^*$ that minimizes the functional
\begin{equation}
    \J(\ac) = \cost_f(\st(t_f),t_f) + \int_{t_0}^{t_f} \cost(\st(t),\ac(t),t) dt
\end{equation}
under the assumptions that $\cost_f \in C^2$, the state and control are unconstrained, and $t_0, \st(t_0)$ are fixed. We define the \textit{Hamiltonian} as
\begin{equation}
    \ham(\st(t),\ac(t),\cst(t),t) \vcentcolon= \cost(\st(t),\ac(t),t) + \cst^T(t) \f(\st(t),\ac(t),t).
\end{equation}
Then, the necessary conditions are 
\begin{align}
\label{eq:nec_ham_conds1}
    \stdot^*(t) &= \frac{\partial \ham}{\partial \cst}(\st^*(t),\ac^*(t),\cst^*(t),t)\\
    \dot{\cst}^*(t) &= -\frac{\partial \ham}{\partial \st}(\st^*(t),\ac^*(t),\cst^*(t),t)\\
    0 &= \frac{\partial \ham}{\partial \ac}(\st^*(t),\ac^*(t),\cst^*(t),t)
    \label{eq:nec_ham_conds3}
\end{align}
which must hold for all $t \in [t_0,t_f]$. Additionally, the boundary conditions 
\begin{align}
\label{eq:ham_bcs}
    [\frac{\partial \cost_f}{\partial \st}(\st^*(t_f),t_f)& - \cst^*(t_f)]^T \delta \st_f\\
    & + [ \ham(\st^*(t_f),\ac^*(t_f), \cst^*(t_f), t_f) + \frac{\partial \cost_f}{\partial t}(\st^*(t_f),t_f)] \delta t_f = 0 \nonumber
\end{align}
must be satisfied. Note that as in the previous section, they are automatically satisfied if the terminal state and time are fixed. Based on these necessary conditions, we have a set of $2n$ \textit{first-order} differential equations (for the state and co-state), and a set of $m$ algebraic equations (control equations). The solution to the state and co-state equations will contain $2n$ constants of integration. To solve for these constants, we use the initial conditions $\st(t_0) = \st_0$ (of which there are $n$), and an additional $n$ (or $n+1$) equations from the boundary conditions. We are left with a two-point boundary value problem, which are considerably more difficult to solve than initial value problems which can just be integrated forward. For a full review of boundary conditions, we again refer the reader to \cite{kirk2012optimal}.

\subsubsection{Proof of the Necessary Conditions}

We will now prove the necessary conditions, (\ref{eq:nec_ham_conds1} -- \ref{eq:nec_ham_conds3}), along with the boundary conditions (\ref{eq:ham_bcs}). For simplicity, assume that the terminal cost is zero, and that $t_f, \st(t_f)$ are fixed and given. Consider the augmented cost function 
\begin{equation}
\hat{\cost}(\st(t), \stdot(t), \ac(t), \cst(t),t) \vcentcolon= \cost(\st(t),\ac(t),t) + \cst^T(t) [\f(\st(t),\ac(t),t) - \stdot(t)].
\end{equation}
When the constraint holds, this augmented cost function is exactly equal to the original cost function. The augmented total cost is then
\begin{equation}
    \hat{\J}(\ac) = \int_{t_0}^{t_f} \hat{\cost}(\st(t), \stdot(t), \ac(t), \cst(t),t) dt.
\end{equation}
Applying the fundamental theorem of CoV on an extremal, we have
\begin{align}
    0 = &\delta \hat{\J}(\ac) = \int_{t_0}^{t_f} \left[ \overbrace{\frac{\partial \hat{\cost}}{\partial \st}(\st^*(t), \stdot^*(t), \ac^*(t), \cst^*(t),t)}^{\frac{\partial \cost}{\partial \st}(\st^*(t),  \ac^*(t), t) + \frac{\partial \f}{\partial \st}^T(\st^*(t),  \ac^*(t), t)\cst^*(t)} - \overbrace{\frac{d}{dt} \frac{\partial \hat{\cost}}{\partial \stdot}(\st^*(t), \stdot^*(t), \ac^*(t), \cst^*(t),t)}^{-\frac{d}{dt}(-\cst^*(t))} \right]^T \delta \st(t) \\
    & + \left[ \frac{\partial \hat{\cost}}{\partial \ac}(\st^*(t), \stdot^*(t), \ac^*(t), \cst^*(t),t)\right]^T \delta \ac(t) + \underbrace{\left[\frac{\partial \hat{\cost}}{\partial \cst}(\st^*(t), \stdot^*(t), \ac^*(t), \cst^*(t),t) \right]^T }_{\f(\st^*(t),\ac^*(t),t) - \stdot^*(t)} \delta \cst(t) dt \nonumber.
\end{align}
Considering each term in sequence, we have:
\begin{itemize}
    \item $\f(\st^*(t),\ac^*(t),t) - \stdot^*(t) = 0$ on an extremal.
    \item The Lagrange multipliers are arbitrary, so we can select them to make the coefficients of $\delta \st(t)$ equal to zero, giving $\dot{\cst}(t) = -\frac{\partial \cost}{\partial \st}(\st^*(t),  \ac^*(t), t) - \frac{\partial \f}{\partial \st}^T(\st^*(t),  \ac^*(t), t)\cst^*(t)$.
    \item The remaining variation $\delta \ac(t)$ is independent, so its coefficient must be zero, thus $ \frac{\partial \cost}{\partial \ac}(\st^*(t),  \ac^*(t), t) + \frac{\partial \f}{\partial \ac}^T(\st^*(t),  \ac^*(t), t)\cst^*(t) = 0$.
\end{itemize}
These conditions exactly give the necessary conditions as previously stated, when recast with the Hamiltonian formalism.

\subsection{Pontryagin's Minimum Principle}

So far, we have assumed that the admissible controls and states are unconstrained. This assumption is frequently violated for real systems---physical actuators have limits on their realizable outputs, and state constraints may occur due to safety considerations. The control $\ac^*$ causes the functional $\J$ to have a relative minimum if
\begin{equation}
    \J(\ac) - \J(\ac^*) = \Delta \J \geq 0
\end{equation}
for all admissible controls ``close'' to $\ac^*$. Letting $\ac = \ac^* + \delta \ac$, the increment can be expressed as
\begin{equation}
    \Delta \J(\ac^*,\delta\ac) = \delta \J(\ac^*,\delta \ac) + \text{higher order terms}.
\end{equation}
The variation $\delta \ac$ is arbitrary only if the extremal control is strictly within the boundary for all time in the interval $[t_0,t_f]$. In general, however, an extremal control lies on a boundary during at least subinterval in the interval $[t_0,t_f]$.
As a consequence, admissible control variations $\delta \ac$ exist whose negatives are not admissible. This implies that a necessary condition for $\ac^*$ to minimize $\J$ is $\delta \J(\ac^*, \delta \ac) \geq 0$ for all admissible variations with $\|\delta \ac\|$ small enough. The reason why the equality in the fundamental theorem of CoV (in which we explicitly assumed no constraints) is replaced with an inequality is the presence of the control constraints. This result has an analogue in calculus, where the necessary condition for a scalar function $f$ to have a relative minimum at the end point is that the differential $df \geq 0$.

Assuming bounded controls $\ac \in \mathcal{U}$, the necessary optimality conditions are 
\begin{align}
    \label{eq:nec_pmp_conds1}
    \stdot^*(t) &= \frac{\partial \ham}{\partial \cst}(\st^*(t),\ac^*(t),\cst^*(t),t)\\
    \dot{\cst}^*(t) &= -\frac{\partial \ham}{\partial \st}(\st^*(t),\ac^*(t),\cst^*(t),t)\\
    \ham(\st^*(t),\ac^*(t), \cst^*(t), t) &\leq \ham(\st^*(t),\ac(t), \cst^*(t), t) \,\,\forall \ac \in \mathcal{U}
    \label{eq:nec_pmp_conds3}
\end{align}
along with the boundary conditions
\begin{align}
\label{eq:ham_bcs}
    [\frac{\partial \cost_f}{\partial \st}(\st^*(t_f),t_f)& - \cst^*(t_f)]^T \delta \st_f\\
    & + [ \ham(\st^*(t_f),\ac^*(t_f), \cst^*(t_f), t_f) + \frac{\partial \cost_f}{\partial t}(\st^*(t_f),t_f)] \delta t_f = 0. \nonumber
\end{align}
The control $\ac^*(t)$ causes $\ham(\st^*(t),\ac^*(t),\cst^*(t),t)$ to assume its global minimum. This is a harder condition, in general, to analyze. Finally, we have additional necessary conditions. If the final time is fixed and the Hamiltonian does not explicitly depend on time, 
\begin{equation}
    \ham(\st^*(t),\ac^*(t),\cst^*(t)) = c \,\, \forall t \in [t_0,t_f]
\end{equation}
and if the final time is free and the Hamiltonian does not depend explicitly on time, 
\begin{equation}
    \ham(\st^*(t),\ac^*(t),\cst^*(t)) = 0 \,\, \forall t \in [t_0,t_f].
\end{equation}
Note that in general, uniqueness and existence are not guaranteed in the constrained setting. 

% TODO add example problems

\subsection{Numerical Aspects of Indirect Optimal Control}

% Mention how PMP can be leveraged to swap the original optimal control problem into a two-point boundary value problem (TPBVP).

% - Pros: We considerably decrease the dimension of the problem because, instead of looking for a control in the very large space $L^{\infty}$, we look for a vector (that is $p(0)$) in the smaller space $\mathbb{R}^n$. Still, this problem is hard to solve.
% - Cons: A good guess of $p(0)$ must be available to make the method converge. The mathematical analysis to get further insights concerning such guess might be difficult.
% Show how to go from PMP to TPBVP for the simple case "fixed final time/fixed final point". Follow the slides of lecture 10 and introduce the "shooting function" $S$ describing all the steps. Therefore, introduce the "indirect shooting method" as research of zeros for the shooting function.
% Reproduce/show how to adapt the argument above in the presence of either "free final time" or "final point belonging to some submanifold", or both. For "final point belonging to some submanifold", attentively introduce the relation that relates the adjoint vector at the final time $p(t_f)$ with the kernel of the function $F$ that defines the submanifold $M_f = \{x\in\mathbb{R}^n|F(x)=0\}$.

\subsection{Further Reading}

For a practical treatment of indirect methods, we refer the reader to \cite{bryson1975applied}. For a more theoretical treatment, we refer the reader to \cite{lee1967foundations}.